package C.栈;

import java.util.Stack;

public class _844_比较含退格的字符串 {
    /**
     * 自解：利用栈进行删除 对比
     * @param S
     * @param T
     * @return
     */
    public boolean backspaceCompare(String S, String T) {

        char[] char_S = S.toCharArray();
        char[] char_T = T.toCharArray();

        Stack<Character> s = new Stack<>();
        Stack<Character> t = new Stack<>();

        for (char c:char_S){
            if (c == '#'){
                if (s.isEmpty()){
                    continue;
                }else {
                    s.pop();
                }

            }else {
                s.push(c);
            }
        }
        for (char c:char_T){
            if (c == '#'){
                if (t.isEmpty()){
                    continue;
                }else {
                    t.pop();
                }

            }else {
                t.push(c);
            }
        }


        if (s.size() != t.size()){
            return false;
        }else if (s.isEmpty() && t.isEmpty()){
            return true;
        }

        while ( !s.isEmpty() || !t.isEmpty()){
            if (s.peek().equals(t.peek())){
                s.pop();
                t.pop();
                continue;
            }else {
                return false;
            }
        }
        return true;
    }

    /**
     * 题解；双指针法：因为后一个#会删除前一个 所以就从后向前遍历===
     * string遍历每一个字符 不需要弄到char【】 用charAt函数就可以
     * dCount是目前遍历到的#数
     * 如果遇到# dCount+1 遍历指针-1
     * 如果没有# 遍历到数字 就等另一个string到数字 两数字进行对比
     */
    public boolean backspaceCompare1(String S, String T) {
        if (S== null || T==null){
            return false;
        }
        int i = S.length()-1;
        int j = T.length()-1;
        int dCount_s =0,dCount_t =0;
        while (i>= 0 || j>=0){

            //遍历s串
            while (i>= 0){
                if (S.charAt(i) == '#'){
                    dCount_s++;
                    i--;
                }else if (dCount_s>0){
                    dCount_s--;
                    i--;
                }else {
                    break;
                }
            }
            //遍历T串
            while (j>= 0){
                if (T.charAt(j) == '#'){
                    dCount_t++;
                    j--;
                }else if (dCount_t>0){
                    dCount_t--;
                    j--;
                }else {
                    break;
                }
            }

            if (i >=0 && j>= 0){
                if (S.charAt(i) != T.charAt(j)){
                    return false;
                }else {
                    i--;
                    j--;
                    continue;
                }
            }else {
                    //return false;//如果直接返回 在两个都清空的情况下 返回错误
                if (i>= 0 || j >= 0){
                    return false;
                }

            }
        }
        return  true;
    }
}
